#include "../include/common.h"
#include "../include/brute_force.h"
#include "../include/dp.h"
#include "../include/greedy.h"
#include "../include/backtrack.h"

// 测试规模：物品数量从1000到320000
const int TEST_SIZES[] = {
    1000, 2000, 3000, 4000, 5000, 6000, 7000, 8000, 9000, 10000,
    20000, 40000, 80000, 160000, 320000
};
const int NUM_TEST_SIZES = sizeof(TEST_SIZES) / sizeof(TEST_SIZES[0]);

// 测试背包容量：10000, 100000, 1000000
const int CAPACITIES[] = {10000, 100000, 1000000};
const int NUM_CAPACITIES = sizeof(CAPACITIES) / sizeof(CAPACITIES[0]);

/**
 * 运行单个测试用例
 * @param n 物品数量
 * @param capacity 背包容量
 */
void run_test(int n, int capacity) {
    char filename[256];
    // 生成数据文件名，例如：data/data_1000.csv
    sprintf(filename, "data/data_%d.csv", n);
    
    // 生成随机测试数据
    generate_data(n, filename);
    
    // 读取生成的测试数据
    int item_count;
    Item* items = read_data(filename, &item_count);
    if (!items) {
        printf("Failed to read data for n=%d\n", n);
        return;
    }

    // 存储四种算法的运行结果
    Result results[4];
    const char* algorithm_names[] = {
        "Brute Force", "Dynamic Programming",
        "Greedy", "Backtracking"
    };

    // 蛮力法（仅在小规模时运行，因为时间复杂度为O(2^n)）
    if (n <= 20) {
        results[0] = brute_force_knapsack(items, n, capacity);
        print_result(&results[0], algorithm_names[0]);
    }

    // 动态规划法（时间复杂度O(nC)，空间复杂度O(nC)）
    results[1] = dp_knapsack(items, n, capacity);
    print_result(&results[1], algorithm_names[1]);

    // 贪心法（时间复杂度O(nlogn)，空间复杂度O(n)）
    results[2] = greedy_knapsack(items, n, capacity);
    print_result(&results[2], algorithm_names[2]);

    // 回溯法（仅在小规模时运行，因为时间复杂度为O(2^n)）
    if (n <= 100) {
        results[3] = backtrack_knapsack(items, n, capacity);
        print_result(&results[3], algorithm_names[3]);
    }

    // 保存结果到CSV文件，文件名格式：data/results_物品数量_背包容量.csv
    sprintf(filename, "data/results_%d_%d.csv", n, capacity);
    for (int i = 0; i < 4; i++) {
        // 只保存实际运行的算法的结果
        if ((i == 0 && n <= 20) || (i == 3 && n <= 100) || (i != 0 && i != 3)) {
            save_result(&results[i], algorithm_names[i], n, capacity, filename);
        }
    }

    // 释放内存
    free_items(items);
}

int main() {
    // 初始化随机数生成器
    srand((unsigned)time(NULL));

    // 创建汇总结果文件，包含表头
    FILE* fp = fopen("data/results.csv", "w");
    if (fp) {
        // CSV文件表头：算法名称,物品数量,背包容量,总价值,执行时间,内存使用
        fprintf(fp, "Algorithm,N,Capacity,TotalValue,TimeTaken,MemoryUsed\n");
        fclose(fp);
    }

    // 对每种背包容量进行测试
    for (int i = 0; i < NUM_CAPACITIES; i++) {
        printf("\nTesting with capacity %d:\n", CAPACITIES[i]);
        // 对每种物品数量进行测试
        for (int j = 0; j < NUM_TEST_SIZES; j++) {
            printf("\nTesting with %d items:\n", TEST_SIZES[j]);
            run_test(TEST_SIZES[j], CAPACITIES[i]);
        }
    }

    return 0;
} 